package com.sheng.leetcode.year2025.month08.day12;

import org.junit.Test;

/**
 * @author by ls
 * @date 2025/8/12
 * <p>
 * 2787. 将一个数字表示成幂的和的方案数<p>
 * <p>
 * 给你两个 正 整数 n 和 x 。<p>
 * 请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。<p>
 * 换句话说，你需要返回互不相同整数 [n1, n2, ..., nk] 的集合数目，满足 n = n1^x + n2^x + ... + nk^x 。<p>
 * 由于答案可能非常大，请你将它对 10^9 + 7 取余后返回。<p>
 * 比方说，n = 160 且 x = 3 ，一个表示 n 的方法是 n = 2^3 + 3^3 + 5^3 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：n = 10, x = 2<p>
 * 输出：1<p>
 * 解释：我们可以将 n 表示为：n = 3^2 + 1^2 = 10 。<p>
 * 这是唯一将 10 表达成不同整数 2 次方之和的方案。<p>
 * <p>
 * 示例 2：<p>
 * 输入：n = 4, x = 1<p>
 * 输出：2<p>
 * 解释：我们可以将 n 按以下方案表示：<p>
 * - n = 4^1 = 4 。<p>
 * - n = 3^1 + 1^1 = 4 。<p>
 * <p>
 * 提示：<p>
 * 1 <= n <= 300<p>
 * 1 <= x <= 5<p>
 */
public class LeetCode2787 {

    @Test
    public void test() {
//        int n = 10, x = 2;
//        int n = 4, x = 1;
        int n = 101, x = 1;
        System.out.println(new Solution().numberOfWays(n, x));
    }
}

class Solution {
    int numberOfWays(int n, int x) {
        long[] f = new long[n + 1];
        f[0] = 1;
        // 本题数据范围小，Math.pow 的计算结果一定准确
        for (int i = 1; Math.pow(i, x) <= n; i++) {
            int v = (int) Math.pow(i, x);
            for (int s = n; s >= v; s--) {
                f[s] += f[s - v];
            }
        }
        return (int) (f[n] % 1_000_000_007);
    }
}

// 超时
//class Solution {
//
//    private static final int MOD = 1000000007;
//
//    int ans = 0;
//
//    int x;
//
//    public int numberOfWays(int n, int x) {
//        this.x = x;
//        dfs(n, n);
//        return ans;
//    }
//
//    public void dfs(int max, int n) {
//        for (int i = max; i >= 1; i--) {
//            if ((int) Math.pow(i, x) == n) {
//                ans++;
//            } else if ((int) Math.pow(i, x) < n) {
//                dfs(i - 1, n - (int) Math.pow(i, x));
//            }
//        }
//    }
//}
